import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/24 11:32
 * @description 01字典树，在线版，直接全部插入数，然后判断时添加限制条件
 */
public class Solution2 {
    public static void main(String[] args) {

    }
    public int[] maximizeXor(int[] nums, int[][] queries) {
        Trie01 trie = new Trie01();
        for (int val : nums) {
            trie.insert(val);
        }
        int numQ = queries.length;
        int[] ans = new int[numQ];
        for (int i = 0; i < numQ; ++i) {
            ans[i] = trie.getMaxXorWithLimit(queries[i][0], queries[i][1]);
        }
        return ans;
    }
}
class Trie01 {
    static final int L = 30;
    Trie01[] children = new Trie01[2];
    /**
     * 表示以该节点为根的子树所记录的元素的最小值
     */
    int min = Integer.MAX_VALUE;

    public void insert(int val) {
        Trie01 node = this;
        node.min = Math.min(node.min, val);
        for (int i = L ; i >= 0; --i) {
            int bit = (val >> i) & 1;
            if (node.children[bit] == null) {
                node.children[bit] = new Trie01();
            }
            node = node.children[bit];
            // 维护每个节点的最小值
            node.min = Math.min(node.min, val);
        }
    }

    public int getMaxXorWithLimit(int val, int limit) {
        Trie01 node = this;
        // 如果最小值都大于limit，直接返回
        if (node.min > limit) {
            return -1;
        }
        int ans = 0;
        for (int i = L ; i >= 0; --i) {
            int bit = (val >> i) & 1;
            // 判断条件增加了一个限制
            if (node.children[bit ^ 1] != null && node.children[bit ^ 1].min <= limit) {
                ans |= 1 << i;
                bit ^= 1;
            }
            node = node.children[bit];
        }
        return ans;
    }
}
